/**
 * 动态规划，4个节点时，左右分别为3,0；2,1；1,2；0,3种情况
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    // n个节点时，能有的二叉树种类
    let dp = [1,1,2]
    if(n<=2) return dp[n]
    for(let i =3;i<=n;i++){
        dp.push(getNcount(i,dp))
    }
    return dp[n]
};

function getNcount(n,dp){
    let count = 0;
    for (let i = n-1;i>=~~(n/2);i--){
        if(i === ~~(n/2) && n%2!==0){
            count+=dp[i]*dp[n-i-1]
        }else{
            count+=dp[i]*dp[n-i-1]*2
        }
    }
    return count
}



/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    // n个节点时，能有的二叉树种类
    let dp = new Array(n+1).fill(0);
    dp[0] = 1;   // 只是为了后面乘积时，不为0
    dp[1] = 1;

    for(let i = 2;i<=n;i++){
        for(let j = 1;j<=i;j++){
            dp[i] += dp[j-1]*dp[i-j]
        }
    }

    return dp[n]
};





const [totalPrice, num] = readline().split(' ').map(Number)
function main(tp, num) {
    // 主件
    const mains = {}
    // 副件
    const subParts = {}
      
    for (let i = 1; i <= num; i++) {
        const [v, p, q] = readline().split(' ').map(Number)
        if (q === 0) {
            mains[i] = [v, p]
        } else {
            if (q in subParts) {
                // 第二个副件
                subParts[q].push([v, p])
            } else {
                // 第一个副件
                subParts[q] = [[v, p]]
            }
        }
    }
      
    // w[i][j] 表示 i 号主件的第j种组合情况时的价格，j有4个值，表示主件及其副件可能的以下四种组合方式：
    // 1. 主件
    // 2. 主件+副件1
    // 3. 主件+副件2
    // 4. 主件+副件1+副件2
    const w = []
    // v[i][j] 和 w[i][j] 对应，表示i号主件的第j种组合情况时的满意度，即价格*重要度
    const v = []
      
    for (const i in mains) {
        // 只有主件时
        const _w = [mains[i][0]]
        const _v = [mains[i][0] * mains[i][1]]
          
        if (i in subParts) {
            const sub = subParts[i]
            // 主件+副件1
            _w.push(mains[i][0] + sub[0][0])
            _v.push(mains[i][0] * mains[i][1] + sub[0][0] * sub[0][1])
            if (sub.length > 1) {
                // 主件 + 副件2
                _w.push(mains[i][0] + sub[1][0])
                _v.push(mains[i][0] * mains[i][1] + sub[1][0] * sub[1][1])
                // 主件 + 副件1 + 副件2
                _w.push(mains[i][0] + sub[0][0] + sub[1][0])
                _v.push(mains[i][0] * mains[i][1] + sub[0][0] * sub[0][1] + sub[1][0] * sub[1][1])
            }
        }
        w.push(_w)
        v.push(_v)
    }
    const dp = new Array(tp + 1).fill(0);
    for (let i = 0; i < w.length; i++) {
        for (let j = tp; j >= 0; j -= 10) {
            let max = dp[j];
            for (let k = 0; k < w[i].length; k++) {
                if (j >= w[i][k]) {
                    max = Math.max(max, dp[j - w[i][k]] + v[i][k]);
                }
            }
            dp[j] = max;
        }
    }
    return dp[tp];
}
console.log(main(totalPrice, num))